package com.gitee.hellowllh.dlearn.algorithm.leetcode.basic.arrarys;

import org.junit.Before;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.Parameterized;

import java.util.*;


import java.util.Arrays;
        import java.util.Collection;

        import org.junit.Before;
        import org.junit.Test;
        import org.junit.runner.RunWith;
        import org.junit.runners.Parameterized;
        import org.junit.runners.Parameterized.Parameters;

import static org.junit.Assert.assertArrayEquals;
import static org.junit.Assert.assertEquals;

/**
 * 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
 *
 * 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
 *
 * 你可以按任意顺序返回答案。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：nums = [2,7,11,15], target = 9
 * 输出：[0,1]
 * 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
 * 示例 2：
 *
 * 输入：nums = [3,2,4], target = 6
 * 输出：[1,2]
 * 示例 3：
 *
 * 输入：nums = [3,3], target = 6
 * 输出：[0,1]
 *  
 *
 * 提示：
 *
 * 2 <= nums.length <= 104
 * -109 <= nums[i] <= 109
 * -109 <= target <= 109
 * 只会存在一个有效答案
 * 进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？
 *
 * 通过次数2,264,938提交次数4,389,165
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/two-sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
//(1)步骤一：测试类指定特殊的运行器org.junit.runners.Parameterized ,表示该类将不使用Junit内建的运行器运行，而使用参数化运行器运行
@RunWith(Parameterized.class)
public class SumOfTwoNumbers {

    // (2)步骤二：为测试类声明几个变量，分别用于存放期望值和测试所用数据。
    private int[] nums;
    private int target;
    private int[] retr;
    @Before
    public void setUp() {
    }

    // (3)步骤三：为测试类声明一个带有参数的公共构造函数，并在其中为第二个环节中声明的几个变量赋值。
    public SumOfTwoNumbers(int[] nums, int target, int[] retr) {
        this.nums = nums;
        this.target = target;
        this.retr = retr;
    }

    // (4)步骤四：为测试类声明一个使用注解 org.junit.runners.Parameterized.Parameters 修饰的，返回值为
    // java.util.Collection 的公共静态方法，并在此方法中初始化所有需要测试的参数对。
    @Parameters
    public static Collection prepareData() {
        // 示例:
        Object[][] object = {
                { new int[]{ 2,7,11,15 }, 9, new int[]{ 0,1 } } ,
                { new int[]{ 3,2,4 }, 6, new int[]{ 1,2 } } ,
                { new int[]{ 3,3 }, 6, new int[]{ 0,1 } } ,
        };
        return Arrays.asList(object);// 数组转化成集合形式。
    }

    // (5)步骤五：编写测试方法，使用定义的变量作为参数进行测试。
    @Test
    public void testOk() {
        // 注意是调用的成员变量。
        assertArrayEquals(this.retr,  this.twoSum(this.nums,this.target) );
    }
    @Test
    public void testOk2() {
        // 注意是调用的成员变量。
        assertArrayEquals(this.retr,  this.twoSum2(this.nums,this.target) );
    }

    // (6) 解法1:
    // 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
    // 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现

    /**
     *
     * 2层遍历,时间复杂度O(n平方2);
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
//            for (int j = i; j < nums.length; j++) {
            //数组中同一个元素在答案里不能重复出现  i+1.
            for (int j = i+1; j < nums.length; j++) {
                if(  nums[i] + nums[j] == target)
                    return new int[]{i,j};
            }
        }
        return new int[2];
    }

    /**
     * 进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum2(int[] nums, int target) {
        HashMap<Integer,Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            // 判断差值是否存在,不存在放入,存在就返回.
//            if(map.containsKey(target-i)){
//                return new int[]{
////                        i ,  map.get(target-i)
//                        map.get(target-i) , i
//                };
//            }

            // 判断差的值，是否存在
            if(map.containsKey(target-nums[i])){
                return new int[]{
                        // 存在的,之前放入的
                        map.get(target-nums[i]) , i
                };
            }
            map.put(nums[i],i);
        }
        return new int[2];
    }



    // 官方答案解析:
    /*
    方法一：暴力枚举
思路及算法

最容易想到的方法是枚举数组中的每一个数 x，寻找数组中是否存在 target - x。

当我们使用遍历整个数组的方式寻找 target - x 时，需要注意到每一个位于 x 之前的元素都已经和 x 匹配过，因此不需要再进行匹配。而每一个元素不能被使用两次，所以我们只需要在 x 后面的元素中寻找 target - x。

代码

JavaC++CPython3Golang

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }
}
复杂度分析

时间复杂度：O(N^2)O(N
2
 )，其中 NN 是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次。

空间复杂度：O(1)O(1)。

方法二：哈希表
思路及算法

注意到方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。

使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N)O(N) 降低到 O(1)O(1)。

这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。

代码

JavaC++CPython3Golang

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; ++i) {
            if (hashtable.containsKey(target - nums[i])) {
                return new int[]{hashtable.get(target - nums[i]), i};
            }
            hashtable.put(nums[i], i);
        }
        return new int[0];
    }
}
复杂度分析

时间复杂度：O(N)O(N)，其中 NN 是数组中的元素数量。对于每一个元素 x，我们可以 O(1)O(1) 地寻找 target - x。

空间复杂度：O(N)O(N)，其中 NN 是数组中的元素数量。主要为哈希表的开销。

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/two-sum/solution/liang-shu-zhi-he-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */


    /**
     * 总结:
     *    可以利用 hashMap , 代替重复查找内容。
     */

}
